λ¬Έμ
Programmers - μ¬λΌμ§λ λ°ν
π Logic
private Result dfs(int aX, int aY, int bX, int bY, int moveA, int moveB) {
boolean win = false;
int minCount = 5 * 5;
int maxCount = moveA + moveB;
if (moveA == moveB && board[aX][aY] == 1) {
// aκ° μμ§μΌ μ°¨λ‘
for (int[] d : dir) {
int naX = aX + d[0];
int naY = aY + d[1];
if (!checkBoundary(naX, naY)) continue;
board[aX][aY] = 0;
Result r = dfs(naX, naY, bX, bY, moveA + 1, moveB);
win |= !r.win;
if (!r.win) minCount = Math.min(minCount, r.count);
else maxCount = Math.max(maxCount, r.count);
board[aX][aY] = 1;
}
} else if (moveA > moveB && board[bX][bY] == 1) {
// bκ° μμ§μΌ μ°¨λ‘
for (int[] d : dir) {
int nbX = bX + d[0];
int nbY = bY + d[1];
if (!checkBoundary(nbX, nbY)) continue;
board[bX][bY] = 0;
// dfsμ κ²°κ³Όλ λ³ΈμΈμ΄ μλ λ€λ₯Έ μ¬λμ κ²°κ³Όμ΄λ―λ‘, μΉν¨κ° λ°λμ΄λ€.
// λν r.win = trueμΈ κ²½μ°κ° νλλΌλ μμ κ²½μ° winμ trueκ° λμ΄μΌ νλ―λ‘ orμ°μ°μ μννλ€.
Result r = dfs(aX, aY, nbX, nbY, moveA, moveB + 1);
win |= !r.win;
// λ³ΈμΈμ΄ μ΄κΈ°λ κ²½μ°λΌλ©΄ μ΅λν 빨리 μ΄κΈΈ λμ μ΄λνμλ₯Ό κ°±μ νλ€.
if (!r.win) minCount = Math.min(minCount, r.count);
// λ³ΈμΈμ΄ μ§λ κ²½μ°λΌλ©΄ μ΅λν μ€λ λ²νΈ λμ μ΄λνμλ₯Ό κ°±μ νλ€.
else maxCount = Math.max(maxCount, r.count);
board[bX][bY] = 1;
}
}
return new Result(win, win ? minCount : maxCount);
}
- Aκ° μμ§μΌ μ°¨λ‘μ, Bκ° μμ§μΌ μ°¨λ‘λ₯Ό λλμ΄ μκ°νλ€.
- DFSλ°©μμΌλ‘ μμ§μ΄λ©΄μ, μ΄κΈ°λ κ²½μ°μ μ§λ κ²½μ°μ μ΄λνμλ₯Ό κ°±μ νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Result {
boolean win;
int count;
public Result(boolean win, int count) {
this.win = win;
this.count = count;
}
}
class Solution {
static int[][] dir = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};
static int[][] board;
static int N;
static int M;
public int solution(int[][] board, int[] aloc, int[] bloc) {
this.board = board;
this.N = board.length;
this.M = board[0].length;
return dfs(aloc[0], aloc[1], bloc[0], bloc[1], 0, 0).count;
}
private Result dfs(int aX, int aY, int bX, int bY, int moveA, int moveB) {
boolean win = false;
int minCount = 5 * 5;
int maxCount = moveA + moveB;
if (moveA == moveB && board[aX][aY] == 1) {
// aκ° μμ§μΌ μ°¨λ‘
for (int[] d : dir) {
int naX = aX + d[0];
int naY = aY + d[1];
if (!checkBoundary(naX, naY)) continue;
board[aX][aY] = 0;
Result r = dfs(naX, naY, bX, bY, moveA + 1, moveB);
win |= !r.win;
if (!r.win) minCount = Math.min(minCount, r.count);
else maxCount = Math.max(maxCount, r.count);
board[aX][aY] = 1;
}
} else if (moveA > moveB && board[bX][bY] == 1) {
// bκ° μμ§μΌ μ°¨λ‘
for (int[] d : dir) {
int nbX = bX + d[0];
int nbY = bY + d[1];
if (!checkBoundary(nbX, nbY)) continue;
board[bX][bY] = 0;
// dfsμ κ²°κ³Όλ λ³ΈμΈμ΄ μλ λ€λ₯Έ μ¬λμ κ²°κ³Όμ΄λ―λ‘, μΉν¨κ° λ°λμ΄λ€.
// λν r.win = trueμΈ κ²½μ°κ° νλλΌλ μμ κ²½μ° winμ trueκ° λμ΄μΌ νλ―λ‘ orμ°μ°μ μννλ€.
Result r = dfs(aX, aY, nbX, nbY, moveA, moveB + 1);
win |= !r.win;
// λ³ΈμΈμ΄ μ΄κΈ°λ κ²½μ°λΌλ©΄ μ΅λν 빨리 μ΄κΈΈ λμ μ΄λνμλ₯Ό κ°±μ νλ€.
if (!r.win) minCount = Math.min(minCount, r.count);
// λ³ΈμΈμ΄ μ§λ κ²½μ°λΌλ©΄ μ΅λν μ€λ λ²νΈ λμ μ΄λνμλ₯Ό κ°±μ νλ€.
else maxCount = Math.max(maxCount, r.count);
board[bX][bY] = 1;
}
}
return new Result(win, win ? minCount : maxCount);
}
private boolean checkBoundary(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < M && board[x][y] != 0) ;
}
}
βοΈ Review
- μ΄κΈΈ μ μλ νλ μ΄μ΄λ μ΅λν 빨리 μΉλ¦¬νκ³ , μ§ μλ°μ μλ νλ μ΄μ΄λ μ΅λν μ€λ λ²ν΄λ€λΌλ 쑰건μ μμ΄ μ‘°κΈ λ νΉν λ¬Έμ κ° μλμλμΆλ€.
- μ€λ³΅λλ λ‘μ§μ λΌλ΄μ΄μΌ ν κ² κ°λ€.
- μμ λ§μ§λ§ λ¬Έμ λ μ΄λ ΅λ€ ...